Показано що базовим задачам проблеми комівояжера - симетричним задачам комівояжера (СЗК) і задачам пошуку гамільтонового циклу мінімальної вартості в графі зі зваженими ребрами (ГЗК) - притаманні алгоритмічні особливості, які потребують подальшого вивчення, а саме з'ясовано, що властивість симетрії суттєво впливає на час і точність наближеного розв'язку СЗК, а ГЗК не завжди розв'язана. Висока точність розв'язку СЗК забезпечується шляхом побудови алгоритму, що складається з двох стадій. Трудомісткість наближеного розв'язку СЗК залежить від алгоритмічних властивостей релаксації та способу перетворення. Запропоновано двохетапний алгоритм пошуку розв'язку ГЗК, який спочатку перевіряє з урахуванням структурних характеристик транспортної мережі умови її негамільтоновості. Якщо жодна з них не виконується, то алгоритмом типу гілок і меж здійснюється відсічення негамільтонових циклів. Для обчислення нижніх оцінок вартості шуканого маршруту запропоновано модифікований метод розв'язання задачі про призначення, який встановлює нерозв'язність ГЗК у вершинах дерева розгалужень. За допомгою розробленої програми системи проведено обчислювальний експеримент і аналіз одержаних даних.

  Скачати повний текст